/*
#Copyright (c) 2013, Philippe Bordron <philippe.bordron@gmail.com>
#
# This file is part of SIPPER.
#
# DCC is free software: you can redistribute it and/or modify
# it under the terms of the GNU LESSER GENERAL PUBLIC LICENSE as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
#
# DCC is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU LESSER GENERAL PUBLIC LICENSE for more details.
#
# You should have received a copy of the GNU LESSER GENERAL PUBLIC LICENSE
# along with SIPPER.  If not, see <http://www.gnu.org/licenses/>
*/
package combi.wip.graph.algo.utils.heaps;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;

import combi.utils.Couple;

public class BinaryHeap<T, K extends Comparable<K>> extends Heap<T, K>{

	protected ArrayList<T> tree;
	protected Map<T, Integer> index;
	protected Map<T, K> order;
	protected K max;

	public BinaryHeap(K max)
	{
		this.tree = new ArrayList<T>();
		this.index = new HashMap<T, Integer>();
		this.order = new HashMap<T, K>();
		this.max = max;
	}

	@Override
	public T min() {
		return tree.get(0);
	}
	
	@Override
	public K getKeyMin()
	{
		return order.get(this.min());
	}
	
	
	protected void addLast(T elem, K key)
	{
		tree.add(elem);
		index.put(elem, size()-1);
		order.put(elem, key);
	}

	protected T delete(T elem)
	{
		int i = index.remove(elem);
		order.remove(elem);
		return tree.remove(i);
	}

	protected T removeLast()
	{
		return delete(tree.get(tree.size()-1));
	}

	@Override
	public void insert(T elem, K key) {
		addLast(elem, key);
		consolidateUp(elem);
	}

	@Override
	public T removeMin() {
		T elem = min();
		order.put(elem, max);
		permutation(0, size()-1);
		consolidateDown(min());
		return removeLast();
	}

	@Override
	public void decreaseKey(T elem, K key) {
		order.put(elem,key);
		consolidateUp(elem);		
	}

	@Override
	public int size() {
		return tree.size();
	}

	private boolean lessThan(T o1, T o2)
	{
		return order.get(o1).compareTo(order.get(o2))<0;
	}

	protected int getFather(int pos)
	{
		return ((pos+1)/2)-1;
	}

	protected int getLeftSon(int pos)
	{
		return (pos+1)*2-1;
	}

	protected int getRightSon(int pos)
	{
		return (pos+1)*2;
	}

	protected void consolidateUp(T elem)
	{
		int sonPos = index.get(elem);
		int fatherPos = getFather(sonPos);
		if (fatherPos>=0)
		{
			T father = tree.get(fatherPos);
			if (lessThan(elem,father))
			{
				permutation(fatherPos,sonPos);
				consolidateUp(elem);
			}
		}
	}

	protected void consolidateDown(T elem)
	{
		int son1Pos = getLeftSon(index.get(elem));
		int son2Pos = getRightSon(index.get(elem));
		T tmp = elem;
		if (son1Pos<size())
		{
			T son1 = tree.get(son1Pos);
			if (lessThan(son1, tmp))
			{
				tmp = son1;
			}
		}
		if (son2Pos<size())
		{
			T son2 = tree.get(son2Pos);
			if (lessThan(son2, tmp))
			{
				tmp = son2;
			}
		}
		if (tmp != elem)
		{
			permutation(elem, tmp);
			consolidateDown(elem);
		}
	}

	protected void permutation(int pos1, int pos2)
	{
		T tmp = tree.get(pos1);
		tree.set(pos1, tree.get(pos2));
		tree.set(pos2, tmp);
		index.put(tree.get(pos1), pos1);
		index.put(tree.get(pos2), pos2);
		//System.err.println(pos1 + "<->" + pos2 + ": " + heap);
	}

	protected void permutation(T o1, T o2)
	{
		permutation(index.get(o1), index.get(o2));
	}

	@Override
	public boolean isEmpty() {
		return tree.isEmpty();
	}

	public String toString()
	{
		List<Couple<T,K>> result =new ArrayList<Couple<T,K>>();
		for (Entry<T, K> entry : order.entrySet())
		{
			result.add(new Couple<T,K>(entry.getKey(), entry.getValue()));
		}
		Collections.sort(result, new CompareElem());
		return result.toString();
	}

	public class CompareElem implements Comparator<Couple<T,K>>
	{
		@Override
		public int compare(Couple<T, K> o1, Couple<T, K> o2) {
			return o1.getSecond().compareTo(o2.getSecond());
		}
	}

	@Override
	public void clear() {
		index.clear();
		order.clear();
		tree.clear();
	}
}
